package Algorithm.Tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author cj
 * @Date 2022/11/1 21:41
 */
public class numTrees {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public static int numTrees1(int n) {
        if (n < 2) {
            return 1;
        }
        int[] num = new int[n + 1];
        num[0] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < i + 1; j++) {
                num[i] += num[j - 1] * num[i - j];
            }
        }
        return num[n];
    }

    // 进阶
    public static List<Node> generateTrees(int n) {
        return generate(1, n);
    }

    private static List<Node> generate(int start, int end) {
        List<Node> res = new ArrayList<>();
        if (start > end) {
            res.add(null);
        }
        Node head = null;
        for (int i = start; i < end + 1; i++) {
            head = new Node(i);
            List<Node> lSubs = generate(start, i);
            List<Node> rSubs = generate(i + 1, end);
            for (Node l : lSubs) {
                for (Node r : rSubs) {
                    head.left = l;
                    head.right = r;
                    // 拷贝到结果链表中
                    res.add(cloneTree(head));
                }
            }
        }
        return res;
    }

    private static Node cloneTree(Node head) {
        if (head == null) {
            return null;
        }
        Node res = new Node(head.value);
        res.left = cloneTree(head.left);
        res.right = cloneTree(head.right);
        return res;
    }
}
